/**
 * Created by IntelliJ IDEA.
 * User: Alexander Fedulin
 * Date: 23.10.11
 * Time: 23:20
 * To change this template use File | Settings | File Templates.
 */



import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.io.Reader;
import java.io.Writer;
import java.util.*;

/**
 * @author Alexander Fedulin.
 */
public class NonPalindrome {
    static final String problem_input = "nonPalindrome.in";
    static final String problem_output = "nonPalindrome.out";
    private StringTokenizer st;
    private BufferedReader br;
    private PrintWriter out;
    private String s;
    void load() throws IOException {
        s = nextToken();
    }
    private int z1[];
    private int z2[];
    private int result[];
    void solve() throws Exception {
        int l = 0;
        int r = -1;
        for (int i = 0; i < s.length(); i++)
        {
            z1[i] = 1;
            if (i < r)
                z1[i] = Math.min(z1[r - i + l - 1], r - i) + 1;
            while (i + z1[i] < s.length() && i - z1[i] + 1 >= 0 && s.charAt(i + z1[i]) == s.charAt(i - z1[i] + 1))
                z1[i]++;
            z1[i] = Math.max(z1[i] - 1, 0);
            if (z1[i] > 0 && i + z1[i] > r)
            {
                l = i - z1[i] + 1;
                r = i + z1[i];
            }
        }
        l = 0;
        r = -1;
        for (int i = 0; i < s.length(); i++)
        {
            z2[i] = 1;
            if (i <= r)
                z2[i] = Math.min(z2[r - i + l], r - i + 1);
            while (i + z2[i] - 1 < s.length() && i - z2[i] + 1 >= 0 && s.charAt(i + z2[i] - 1) == s.charAt(i - z2[i] + 1))
                z2[i]++;
            z2[i]--;
            if (i + z2[i] - 1 > r)
            {
                r = i + z2[i] - 1;
                l = i - z2[i] + 1;
            }
        }

        Arrays.fill(result, 0, s.length() + 2, -1);
        int lst[] = new int[2];
        lst[0] = 0;
        for (int i = 1; i < s.length() && s.charAt(i) == s.charAt(i - 1); i++)
            lst[0] = i;
        lst[0]++;
        lst[1] = 1;
        for (int i = 2; i < s.length() && s.charAt(i) == s.charAt(i - 2); i++)
            lst[1] = i;
        lst[1]++;
        for (int i = 2; i <= s.length(); i++)
        {
            if (i % 2 == 0)
            {
                if (lst[0] >= i - 1 && lst[0] < s.length())
                    result[i] = lst[0] - i + 1;
                else if (lst[0] < s.length())
                {
                    if (z1[i / 2 - 1] < i / 2)
                        result[i] = 0;
                    else if (s.length() != i)
                        result[i] = 1;
                }
            }
            else
            {
                if (lst[1] >= i - 1 && lst[1] < s.length())
                        result[i] = lst[1] - i + 1;
                else if (lst[1] < s.length())
                {
                    if (z2[i / 2] < i / 2 + 1)
                        result[i] = 0;
                    else if (i != s.length())
                        result[i] = 1;
                }
            }
        }
        long res = 0;
        for (int i = 1; i <= s.length(); i++)
            res = res * (long)100007 + ((long)result[i] + 1);
        BigInteger llres = BigInteger.valueOf(res);
        BigInteger limit = BigInteger.ONE.shiftLeft(64);
        if (llres.compareTo(BigInteger.ZERO) < 0) llres = llres.add(limit);
        out.println(llres);
    }

    public void run() {
        try {
            boolean oj = System.getProperty("ONLINE_JUDGE") != null;
            Reader reader = oj ? new InputStreamReader(System.in) : new FileReader(problem_input);
            Writer writer = oj ? new OutputStreamWriter(System.out) : new FileWriter(problem_output);
            br = new BufferedReader(reader);
            out = new PrintWriter(writer);
            int T = nextInt();
            z1 = new int[100010];
            z2 = new int[100010];
            result = new int[100010];
            for (int i = 0; i < T; i++)
            {
                load();
                solve();
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(42);
        }
    }

    private String nextToken() throws IOException {
        while (st == null || (!st.hasMoreTokens())) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    void nextArray(int a[], int size) throws IOException {
        a = new int[size];
        for (int i = 0; i < size; i++)
            a[i] = nextInt();
    }

    void nextArray(double a[], int size) throws IOException {
        a = new double[size];
        for (int i = 0; i < size; i++)
            a[i] = nextDouble();
    }

    void nextArray(String a[], int size) throws IOException {
        a = new String[size];
        for (int i = 0; i < size; i++)
            a[i] = nextToken();
    }

    String readAll() throws IOException {
        String a = "";
        st = null;
        while (br.ready())
            a += br.read();
        return a;
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public static void main(String[] args) {
        new NonPalindrome().run();
    }
}

